Counting Solutions to Quadratic Equation Modulo Prime

This result relates to the fact that "square roots" modulo \(p\) where \(p\) is prime come in pairs. This is incredibly useful when counting quadratic residues modulo prime.

Theorem

Given an odd prime \(p\) and \(a \not\equiv 0 \pmod p\), the equation:

\[ x^2 \equiv a \pmod p\]

has either \(2\) or \(0\) solutions modulo \(p\).

Proof

Consider \(x \in \mathbb{Z}_p\), a solution to the equation:

\[ x^2 \equiv a \pmod p\]

where \(a \not\equiv 0 \pmod p\).

Let \(y\) be another such solution. Then consider that

\[\begin{align*} &x^2 - y^2 \equiv a - a \equiv 0 \pmod p \\ \iff& (x - y)(x + y) \equiv 0 \pmod p \\ \iff& x - y \equiv 0 \pmod p \quad \text{or} \quad x + y \equiv 0 \pmod p \tag{1} \\ \iff& x \equiv y \pmod p \quad \text{or} \quad x \equiv -y \pmod p. \\ \end{align*}\]

Where (1) follows since \(p\) being prime implies \(\mathbb{Z}_p\) is a field implies that it has the zero product property since every division ring is a domain. In the case where \(p\) is not a prime, we can only conclude that any two solutions sum to or differ by a zero divisor.

Hence \(y\) is another solution if and only if it is \(-x\) or \(x\). Then consider (in the interest of showing that these are distinct)

\[\begin{align*} &x \equiv -x \pmod p \\ \iff& 2x \equiv 0 \pmod p \\ \iff& x \equiv 0 \pmod p \\ \end{align*}\]

where we once again apply the zero product property for this last step (or more primitively that \(p\) being odd implies that \(\mathrm{gcd}(2, p) = 1\) and hence we may multiply by \(a^{-1}\)).

Given that \(a \not\equiv 0 \pmod p\), we have that \(x \not\equiv 0 \pmod p\) once again from the zero product property applied to \(x \cdot x\).

Then, from the above, this implies that \(-x \not\equiv x \pmod p\), so we have exactly two distinct solutions if any solutions exist.

We can also find a nice expression for the number of solutions to such an equation, with less restrictions on \(a\), however this result depends on Euler's criterion which the above is used to proof (for the proof in this vault).

Assuming we have this result now though, then we have the following corollary.

Corollary

Given an odd prime \(p\) and any integer \(a\), the equation:

\[ x^2 \equiv a \pmod p\]

has \(1 + a^{\frac{p - 1}{2}}\) solutions.

Non-Prime Modulus

Above it was shown that for a non-prime modulus the condition on square roots is that they sum to or differ by a zero divisor. Here is an explicit example showing that there may be more square roots in this case, and how they pair as described above.

Example
\[ x^2 \equiv 1 \pmod 8\]

has \(4\) solutions.

In this case we have that:

\[\begin{align*} &0^2 \equiv 0 \pmod 8 \\ &1^2 \equiv (-1)^2 \equiv 1 \pmod 8 \\ &2^2 \equiv (-2)^2 \equiv 4 \pmod 8 \\ &3^2 \equiv (-3)^2 \equiv 1 \pmod 8 \\ &4^2 \equiv (-4)^2 \equiv 0 \pmod 8 \\ \end{align*}\]

and hence the solutions are the residue classes of \(1\), \(-1\), \(3\) and \(-3\).

In the case of \(\mathbb{Z}_8\) we have zero divisors of \(0\), \(2\) and \(4\), and here:

\[ 1 + 3 = 4, \ 3 - 1 = 2 \quad \text{and} \quad 1 - 1 = 0.\]

Note that these pairs overlap, and the numbers are reused, which is why we don't get as strong of a condition as above for a composite modulus.